// 斐波那契数列--青蛙跳台阶--填方块
#include <iostream>

// 递归版
int R_Fibonacci(int n)
{
    if (n == 1)
        return 1;
    if (n <= 0)
        return 0;

    return R_Fibonacci(n - 1) + R_Fibonacci(n - 2);
}

// 非递归版本
int Finbonacci(int n)
{
    if (n <= 1)
        return n;

    int n1 = 0;
    int n2 = 1;

    for (int i = 2; i < n; i++)
    {
        int n3 = n1 + n2;
        n1 = n2;
        n2 = n3;
    }
    return n1 + n2;
}

void TestFibonacci()
{
    std::cout << R_Fibonacci(0) << std::endl;
    std::cout << R_Fibonacci(1) << std::endl;
    std::cout << R_Fibonacci(2) << std::endl;
    std::cout << R_Fibonacci(3) << std::endl;
    std::cout << R_Fibonacci(4) << std::endl;
    std::cout << R_Fibonacci(5) << std::endl;
    std::cout << R_Fibonacci(6) << std::endl;
    std::cout << R_Fibonacci(7) << std::endl;

    std::cout << "==================================" << std::endl;

    std::cout << Finbonacci(0) << std::endl;
    std::cout << Finbonacci(1) << std::endl;
    std::cout << Finbonacci(2) << std::endl;
    std::cout << Finbonacci(3) << std::endl;
    std::cout << Finbonacci(4) << std::endl;
    std::cout << Finbonacci(5) << std::endl;
}

//青蛙跳台阶问题
int Jump(int n)
{
    if(n <= 1)
        return 1;
    
    return Jump(n - 1) + Jump(n - 2);
}

//填方块问题
int Function(int n)
{
    if(n <= 1)
        return 1;
    
    return Function(n - 1) + Function(n - 2);
}

int main()
{
    // TestFibonacci();
    std::cout << Jump(3) << std::endl;
    return 0;
}